50. Sudoku al estilo de P. Norvig¶

Esta solución al Sudoku es una mínima re-escritura de la solución dada por Peter Norvig en su página.

Los cambios tan solo pretenden eliminar las decisiones sutiles, que no son propias de un aprendiz. Tal es el caso de la codificación de filas, columnas y valores como cadenas para evitar el uso de deepcopy.

Nosotros codificaremos las casillas con sus coordenadas cartesianas, como una simple tupla y los valores como conjuntos de números.

En primer lugar vamos a definir las estructuras que emplea Peter Norvig. Piénsalas tú mismo en casa, no las leas sin más. Escribe tú mismo una función que las calcule y emplea tantas funciones como necesites.

• Cada casilla es una tupla (x,y) con las coordenadas cartesianas.
• squares es una lista de todas las casillas del Sudoku.
• unitlist es una lista de todas las unidades. Una unidad es a su vez una lista de 9 casillas que no pueden contener nada más que una cifra de cada. Es decir, unitlist contiene listas de 9 casillas que corresponden a las filas, columnas y bloques.
• units es un diccionario que asocia con cada casilla del Sudoku todas las unidades a las que pertenece dicha casilla.
• peers (colegas) es un diccionario que asocia a cada casilla del Sudoku la lista de casillas que están en su misma fila, columna o bloque, sin incluirla.

squares = [ (x,y) for y in range(9) for x in range(9) ]
blocks = [ (0,1,2), (3,4,5), (6,7,8) ]
unitlist = [ [ (x,y) for x in range(9) ] for y in range(9) ] + \
            [ [ (x,y) for y in range(9) ] for x in range(9) ] + \
            [ [ (x,y) for x in bx for y in by ] for bx in blocks for by in blocks ]
units = { s: [u for u in unitlist if s in u] for s in squares }
peers = { s: set(sum(units[s],[])) - { s } for s in squares }

Vamos ahora a definir funciones para convertir una cadena de texto a un Sudoku. El Sudoku lo modelaremos como un diccionario que hace corresponder a cada casilla con el conjunto de números que puede contener dicha casilla. Es prácticamente una trasliteración del código de Peter Norvig, por lo que no merece la pena comentarlo con mucho más detalle.

La función ignora cualquier carácter que no sea una cifra o un punto. El punto o el 0 representan casillas sin rellenar.

Inicialmente el Sudoku está vacío. Es decir, cada casilla puede contener cualquier cifra. Lo modelamos con la variable values que no es más que un diccionario que hace corresponder cada casilla al conjunto de valores permitidos en esa casilla. Usamos conjuntos (set) porque se esta forma garantizamos que no hay repetidos y además podemos eliminar elementos empleando el operador de resta.

Cada vez que conocemos una casilla con un dígito fijo (de 1 a 9) podemos asignar ese valor a la casilla eliminado el resto. Esta asignación hace que podamos simplificar otras casillas (propagación de restricciones).

digits = range(1,10)

def parse_grid(grid):
    values = { s:set(digits) for s in squares }
    for s,d in grid_values(grid).items():
        if d in digits:
            asignar(values, s, { d })
    return values

def grid_values(grid):
    values = [ gvalue(c) for c in grid if c in '.1234567890' ]
    assert len(values) == 81
    return dict(zip(squares, values))

def gvalue(c): return int(c) if c in '123456789' else 0

El punto clave de la solución del Sudoku es la propagación de restricciones. Básicamente consiste en la combinación de dos funciones que cooperan entre sí, una para asignar valores a una casilla y otra para eliminar valores de una casilla. Cuando se asigna un valor en una casilla, debe eliminarse de todos sus peers. Al eliminar valores de una casilla puede que queden nuevas casillas con un único valor, que daría lugar a nuevas eliminaciones. También puede que solo quede una casilla posible donde poner alguna de las cifras, por lo que daría lugar a la asignación de esta cifra.

def asignar(values, s, d):
    other_values = values[s] - d
    eliminar(values, s, other_values)

def eliminar(values, s, d):
    if not d.intersection(values[s]):
        return

    values[s] -= d
    if len(values[s]) == 0:
        raise ValueError('Casilla {0} sin valores posibles'.format(s))

    ## (1) Si una casilla se queda con un solo valor, eliminarlo de sus colegas.
    if len(values[s]) == 1:
        for s2 in peers[s]:
            eliminar(values, s2, values[s])

    ## (2) Si solo hay una casilla de una unidad para el digito d asignarlo a esa casilla.
    for u in units[s]:
        dplaces = [s for s in u if d.intersection(values[s])]
        if len(dplaces) == 0:
            raise ValueError('No hay casilla para valor {0} en unidad {1}'.format(d,u))
        elif len(dplaces) == 1:
            asignar(values, dplaces[0], d)

Va siendo hora de escribir una función para mostrar el Sudoku. Dibujaremos líneas para separar los bloques. Lo más destacable es el cálculo del ancho de cada casilla, que depende de cuántas cifras posibles tienen todas las casillas del Sudoku.

def display(values):
    width = 1+max(len(values[s]) for s in squares)
    line = '+'.join(['-'*(width*3)]*3)
    for r in range(9):
        print(''.join(''.join([str(i) for i in values[(c,r)]]).center(width)+('|' if c in (2,5) else '')
                      for c in range(9)))
        if r in (2,5): print(line)
    print()

Solo con esto ya se resuelven prácticamente todos los Sudokus fáciles.

grid1 = '003020600900305001001806400008102900700000008006708200002609500800203009005010300'
display(parse_grid(grid1))

4 8 3 |9 2 1 |6 5 7
9 6 7 |3 4 5 |8 2 1
2 5 1 |8 7 6 |4 9 3
------+------+------
5 4 8 |1 3 2 |9 7 6
7 2 9 |5 6 4 |1 3 8
1 3 6 |7 9 8 |2 4 5
------+------+------
3 7 2 |6 8 9 |5 1 4
8 1 4 |2 5 3 |7 6 9
6 9 5 |4 1 7 |3 8 2

En algunos casos la propagación de restricciones sigue dejando un Sudoku muy poco especificado.

grid2 = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'
display(parse_grid(grid2))

   4      1679   12679  |  139     2369    1269  |   8      1239     5
 26789     3    1256789 | 14589   24569  1245689 | 12679    1249   124679
  2689   15689   125689 |   7     234569 1245689 | 12369   12349   123469
------------------------+------------------------+------------------------
  3789     2     135789 |  3459   34579    4579  | 13579     6     13789
  3679   15679   135679 |  359      8     25679  |   4     12359   12379
 36789     4     356789 |  359      1     25679  | 23579   23589   23789
------------------------+------------------------+------------------------
  289      89     289   |   6      459      3    |  1259     7     12489
   5      6789   36789  |   2      479    14789  |  1369   13489   134689
   1      6789     4    |  589     579     5789  | 23569   23589   23689

Aparentemente el número de posibilidades es aún muy elevado:

def nposibles(values):
    n = 1
    for s,v in values.items():
        n *= len(v)
    return n

print(nposibles(parse_grid(grid2)))

181432630923264000000000000000000000000000

Sin embargo si dirigimos adecuadamente la búsqueda el resultado puede ser muy rápido. Tomar una decisión sobre el valor de una casilla que tiene nueve posibilidades nos da un 11% de probabilidad de acierto. Sin embargo elegir una de las opciones de una casilla que solo tenga dos posibilidades nos da un 50% de probabilidad de acierto, y al propagar las restricciones se reduce la cardinalidad de las demás casillas, aumentando correspondientemente la probabilidad de acierto.

def solve(grid): return search(parse_grid(grid))

from copy import deepcopy

def search(values):
    if all(len(values[s]) == 1 for s in squares):
        return values

    ## Elige la casilla sin fijar con menos posibilidades
    n,s = min((len(values[s]), s) for s in squares if len(values[s]) > 1)
    return intentar_todos(values, s)

def intentar_todos(values, s):
    for d in values[s]:
        try:
            tentativa = deepcopy(values)
            asignar(tentativa, s, { d })
            return search(tentativa)
        except ValueError:
            pass

    raise ValueError('No hay solucion')

display(solve(grid2))

4 1 7 |3 6 9 |8 2 5
6 3 2 |1 5 8 |9 4 7
9 5 8 |7 2 4 |3 1 6
------+------+------
8 2 5 |4 3 7 |1 6 9
7 9 1 |5 8 6 |4 3 2
3 4 6 |9 1 2 |7 5 8
------+------+------
2 8 9 |6 4 3 |5 7 1
5 7 3 |2 9 1 |6 8 4
1 6 4 |8 7 5 |2 9 3

hard1  = '''
. . . |. . 6 |. . .
. 5 9 |. . . |. . 8
2 . . |. . 8 |. . .
------+------+------
. 4 5 |. . . |. . .
. . 3 |. . . |. . .
. . 6 |. . 3 |. 5 4
------+------+------
. . . |3 2 5 |. . 6
. . . |. . . |. . .
. . . |. . . |. . .'''
display(solve(hard1))

3 8 4 |5 1 6 |9 2 7
6 5 9 |4 7 2 |1 3 8
2 7 1 |9 3 8 |6 4 5
------+------+------
8 4 5 |2 6 9 |7 1 3
1 2 3 |7 5 4 |8 6 9
7 9 6 |1 8 3 |2 5 4
------+------+------
9 1 8 |3 2 5 |4 7 6
4 3 2 |6 9 7 |5 8 1
5 6 7 |8 4 1 |3 9 2

hard2 = '''
. . 5 |3 . . |. . .
8 . . |. . . |. 2 .
. 7 . |. 1 . |5 . .
------+------+------
4 . . |. . 5 |3 . .
. 1 . |. 7 . |. . 6
. . 3 |2 . . |. 8 .
------+------+------
. 6 . |5 . . |. . 9
. . 4 |. . . |. 3 .
. . . |. . 9 |7 . . '''
display(solve(hard2))

1 4 5 |3 2 7 |6 9 8
8 3 9 |6 5 4 |1 2 7
6 7 2 |9 1 8 |5 4 3
------+------+------
4 9 6 |1 8 5 |3 7 2
2 1 8 |4 7 3 |9 5 6
7 5 3 |2 9 6 |4 8 1
------+------+------
3 6 7 |5 4 2 |8 1 9
9 8 4 |7 6 1 |2 3 5
5 2 1 |8 3 9 |7 6 4